31. 下一个排列

Similar Question

Solution Tips

方案一: 数学模拟

我们希望下一个数 比当前数大，这样才满足 “下一个排列” 的定义。因此只需要 将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。

我们还希望下一个数 增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：

1. 在 尽可能靠右的低位 进行交换，需要 从后向前 查找
2. 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
3. 将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

以上就是求 “下一个排列” 的分析过程。

function nextPermutation(nums) {
    // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在
    let i = nums.length - 2;
    // 寻找第一个小于右邻居的数
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    // 这个数在数组中存在，从它身后挑一个数，和它换
    if (i >= 0) {
        // 从最后一项，向左遍历
        let j = nums.length - 1;
        // 寻找第一个大于 nums[i] 的数
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        // 两数交换，实现变大
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    // 如果 i = -1，说明是递减排列，如 3 2 1，没有下一排列，直接翻转为最小排列：1 2 3
    let l = i + 1;
    let r = nums.length - 1;
    // i 右边的数进行翻转，使得变大的幅度小一些
    while (l < r) {
        [nums[l], nums[r]] = [nums[r], nums[l]];
        l++;
        r--;
    }

    return nums;
}

console.log(nextPermutation([3, 1, 2]))